home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 2997 < prev    next >
Encoding:
Text File  |  1996-08-06  |  3.6 KB  |  167 lines
  1. Path: cph-1.news.DK.net!dkuug!dknet!usenet
  2. From: cronberg@login.dknet.dk (Michell Cronberg)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Trees !, Who can help me to improve my trees code ! <janc@pi.net>
  5. Date: Sun, 21 Jan 1996 14:30:30 -0100
  6. Organization: DKnet / EUnet Denmark - Login Tjenesten
  7. Message-ID: <Mmb0na-0FxaC078yn@login.dknet.dk>
  8. References: <4dr86i$75f@neptunus.pi.net>
  9. NNTP-Posting-Host: login.dknet.dk
  10.  
  11.         Haven't looked at your code but made my own.
  12.         Mail/post if you have any questions.
  13.  
  14.                 Later,
  15.                 Michell
  16.  
  17. Tree.cpp
  18. --------------------------------------------------------------------------
  19. // Suggestion for TREE (NOT BALANCED) app.
  20. // Copenhagen, Jan 1996
  21. // Michell Cronberg
  22.  
  23. #include <iostream.h>
  24. #include <conio.h>
  25.  
  26. class node                // class for nodes in tree
  27. {
  28.     int value;
  29.     node *left;            // left child
  30.     node *right;            // right child
  31.  
  32.     public:
  33.     node(int val){value=val; left=NULL; right=NULL;};    // constructor
  34.     void shownode(){cout<<"node = "<<value<<endl;};
  35.     friend tree;            // access for tree functions
  36. };
  37.  
  38. class tree
  39. {
  40.     node *first;            // pointer to first node in tree
  41.  
  42.     public:
  43.     tree(){first=NULL;};        // constuctor
  44.     node *getfirst(){return first;};
  45.     int add(int val);               // add node (!recusive)
  46.     int search(int val, node *tmp);    // search for node (!recusive)
  47.     void preordre(node *next);    // traversal algorithm (recusive)
  48.     void inordre(node *next);    // traversal algorithm (recusive)
  49.     void postordre(node *next);     // traversal algorithm (recusive)
  50. };
  51.  
  52. int tree::add(int val)
  53. {
  54.     node *tmp=new node(val);    // node added (wild pointer)
  55.  
  56.     if(first==0)            // first node in tree
  57.     {
  58.         first=tmp;
  59.         cout<<val<<" as no. 1"<<endl;
  60.         return 1;
  61.     };
  62.  
  63.     node *traverse=first;        // tmp pointer used to traverse tree
  64.     node *saveparent=NULL;        // tmp pointer to save parent
  65.     int way;            // var to save if its left or right
  66.                     // child
  67.  
  68.     while(traverse!=NULL)
  69.     {
  70.         saveparent=traverse;    // save parent
  71.  
  72.         if(traverse->value>=val)    // go left in tree
  73.         {
  74.             traverse=traverse->left;
  75.             way=1;
  76.         }
  77.         else                // go right in tree
  78.         {
  79.             traverse=traverse->right;
  80.             way=2;
  81.         }
  82.     };
  83.     // this code hooks the node to the tree as a leave
  84.     if(way==1) saveparent->left=tmp; else saveparent->right=tmp;
  85.  
  86.     cout<<val<<" is added"<<endl;
  87.     return 1;
  88. };
  89.  
  90. int tree::search(int val, node *tmp)        
  91. {
  92.     cout<<"Searching for "<<val<<" = ";
  93.     while(tmp!=NULL)
  94.     {
  95.         if(tmp->value==val)
  96.         {
  97.         cout<<"found"<<endl;
  98.         return 1;            // node found
  99.  
  100.         }
  101.  
  102.         if(tmp->value>=val)        // go left in tree
  103.             tmp=tmp->left;
  104.         else                // go right in tree
  105.             tmp=tmp->right;
  106.     };
  107.     cout<<"not found"<<endl;
  108.     return 0;                // node not found
  109. };
  110.  
  111. void tree::preordre(node *tmp)
  112. // traverse tree preordre - from leave to top (used ei. to delete tree)
  113. {
  114.     if(tmp==first) cout<<"Preordre: "<<endl;
  115.     if(tmp!=0)
  116.     {
  117.       tmp->shownode();
  118.       preordre(tmp->left);
  119.       preordre(tmp->right);
  120.     };
  121. };
  122.  
  123. void tree::inordre(node *tmp)
  124. // traverse tree inordre - sort tree
  125. {
  126.     if(tmp==first) cout<<"Inordre: "<<endl;
  127.     if(tmp!=0)
  128.     {
  129.       inordre(tmp->left);
  130.       tmp->shownode();
  131.       inordre(tmp->right);
  132.     };
  133. };
  134.  
  135. void tree::postordre(node *tmp)
  136. // traverse tree postorder - (top to leave) used ei. to print tree
  137. {
  138.     if(tmp==first) cout<<"Postordre: "<<endl;
  139.     if(tmp!=0)
  140.     {
  141.       postordre(tmp->left);
  142.       postordre(tmp->right);
  143.       tmp->shownode();
  144.     };
  145. };
  146.  
  147. void main()
  148. {
  149.     clrscr();
  150.     tree newtree;
  151.  
  152.     newtree.add(10);
  153.     newtree.add(5);
  154.     newtree.add(1);
  155.     newtree.add(12);
  156.  
  157.     newtree.preordre(newtree.getfirst());
  158.     newtree.inordre(newtree.getfirst());
  159.     newtree.postordre(newtree.getfirst());
  160.  
  161.     newtree.search(5,newtree.getfirst());
  162.     newtree.search(13,newtree.getfirst());
  163.     newtree.search(10,newtree.getfirst());
  164.  
  165. };
  166.  
  167.